UVa/10249 - The grand dinner/10249.cpp

   1 /*
   2   Problem: 10249 - The grand dinner
   3   Andrés Mejía-Posada (andmej@gmail.com)
   4
   5   Time limit exceeded
   6  */
   7 using namespace std;
   8 #include <algorithm>
   9 #include <iostream>
  10 #include <iterator>
  11 #include <sstream>
  12 #include <fstream>
  13 #include <cassert>
  14 #include <climits>
  15 #include <cstdlib>
  16 #include <cstring>
  17 #include <string>
  18 #include <cstdio>
  19 #include <vector>
  20 #include <cmath>
  21 #include <queue>
  22 #include <deque>
  23 #include <stack>
  24 #include <list>
  25 #include <map>
  26 #include <set>
  27
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " is " << x << endl
  30 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  31
  32 const int MAXN = 205;
  33
  34 int cap[MAXN][MAXN];
  35 int flow[MAXN][MAXN];
  36 int prev[MAXN];
  37
  38 bool findPath(int n, int src, int sink){
  39   fill(prev, prev+n, -1);
  40   queue<int> q;
  41   q.push(src);
  42   while (q.size()){
  43     int u = q.front(); q.pop();
  44     if (u == sink) return true;
  45     for (int v = 0; v<n; ++v){
  46       if (v != src && prev[v] == -1 && flow[u][v] < cap[u][v]){
  47         prev[v] = u;
  48         q.push(v);
  49       }
  50     }
  51   }
  52   return false;
  53 }
  54
  55 int maxFlow(int n, int src, int sink){
  56   memset(flow, 0, sizeof flow);
  57   int ans = 0;
  58   while (findPath(n, src, sink)){
  59     int neck = INT_MAX;
  60     for (int u = sink; prev[u] != -1; u = prev[u]){
  61       neck = min(neck, cap[prev[u]][u] - flow[prev[u]][u]);
  62     }
  63     for (int u = sink; prev[u] != -1; u = prev[u]){
  64       flow[prev[u]][u] += neck;
  65       flow[u][prev[u]] -= neck;
  66     }
  67     ans += neck;
  68   }
  69   return ans;
  70 }
  71
  72 int main(){
  73   int nteams, ntables;
  74   while (scanf("%d %d", &nteams, &ntables)==2 && nteams && ntables){
  75     int people = 0;
  76     const int source = nteams + ntables, sink = source + 1;
  77     memset(cap, 0, sizeof cap);
  78     for (int i=0, c; i<nteams; ++i){
  79       scanf("%d", &c);
  80       cap[source][i] = c;
  81       people += c;
  82     }
  83     for (int i=0, c; i<ntables; ++i){
  84       scanf("%d", &c);
  85       cap[nteams+i][sink] = c;
  86     }
  87     for (int i=0; i<nteams; ++i){
  88       for (int j=0; j<ntables; ++j){
  89         cap[i][nteams+j] = 1;
  90       }
  91     }
  92     int f = maxFlow(nteams + ntables + 2, source, sink);
  93     if (f < people){
  94       printf("0\n");
  95     }else{
  96       printf("1\n");
  97       for (int i=0; i<nteams; ++i){
  98         bool first = true;
  99         for (int j=0; j<ntables; ++j){
 100           if (flow[i][nteams+j] > 0){
 101             if (!first) printf(" ");
 102             first = false;
 103             printf("%d", j+1);
 104           }
 105         }
 106         printf("\n");
 107       }
 108     }
 109   }
 110   return 0;
 111 }